package a.codetop.DP;

import org.junit.Test;

public class 最长回文子串 {
    @Test
    public void test() {
        System.out.println(longestPalindrome("babad"));
    }

    public String longestPalindrome (String s) {

        String s1=s, s2=new StringBuilder(s).reverse().toString();

        int[][] dp = new int[s1.length()][s2.length()];

        for (int i = 0; i < s1.length(); i++) {
            dp[i][0]= s1.charAt(i)==s2.charAt(0)?1:0;
        }
        for (int j = 0; j < s2.length(); j++) {
            dp[0][j]= s1.charAt(0)==s2.charAt(j)?1:0;
        }

        int maxLen = 0;
        String maxStr = s.charAt(0)+""; //公共子串至少是一个字符（”a、ac“要用）

        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if(s1.charAt(i)!=s2.charAt(j)) dp[i][j]=0;
                else{
                    dp[i][j]=dp[i-1][j-1]+1;
                    if(dp[i][j]>maxLen) {
                        //比公共子串新增————————————————————————————————————
                        int j_fanzhuanqian_index = s2.length()-1-j;
                        int I = j_fanzhuanqian_index + dp[i][j]-1;
                        if(I==i) {
                        //————————————————————————————————————————————————
                            maxLen = dp[i][j];
                            maxStr = s1.substring(i+1-dp[i][j], i+1);
                        }
                    }
                }
            }
        }

        return maxStr;
    }

}
